package _binary_tree

import common.TreeNode
import org.junit.Assert
import org.junit.Test

/**
 * https://leetcode.cn/problems/diameter-of-binary-tree/description
 *
 * 题型： 二叉树的后序遍历
 *
 * ```
 * 543. 二叉树的直径
 * 给你一棵二叉树的根节点，返回该树的 直径 。
 * 二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
 * 两节点之间路径的 长度 由它们之间边数表示。
 *
 * 示例 1：
 *
 * 输入：root = [1,2,3,4,5]
 * 输出：3
 * 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。
 *
 * 示例 2：
 * 输入：root = [1,2]
 * 输出：1
 *
 *
 * 示例3:
 * 输入：[4,-7,-3,null,null,-9,-3,9,-7,-4,null,6,null,-6,-6,null,null,0,6,5,null,9,null,null,-1,-4,null,null,null,-2]
 * 输出：8
 * ```
 */
class leetcode_543 {
    @Test
    fun test_1() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        val n3 = TreeNode(3)
        val n4 = TreeNode(4)
        val n5 = TreeNode(5)
        n1.left = n2
        n1.right = n3
        n2.left = n4
        n2.right = n5
        val root: TreeNode = n1
        val actual = diameterOfBinaryTree(root)
        val expected = 3
        Assert.assertEquals(expected.toString(), actual.toString());
    }

    @Test
    fun test_2() {
        val n1 = TreeNode(1)
        val n2 = TreeNode(2)
        n1.left = n2
        val root: TreeNode = n1
        val actual = diameterOfBinaryTree(root)
        val expected = 1
        Assert.assertEquals(expected.toString(), actual.toString());
    }

    private fun diameterOfBinaryTree(root: TreeNode?): Int {
        // https://leetcode.cn/problems/diameter-of-binary-tree/solutions/794147/er-cha-shu-de-zhi-jing-by-shen-jing-wa-3-tba6

        /**
        题型： 二叉树的后序遍历（左右中）
        思路：
        涉及三个值：
        最大路径长度 = max(最大路径长度, 当前节点的路径长度)
        当前节点的路径长度 = 当前节点的左孩子最大深度 + 当前的右孩子最大深度
        当前节点的深度 = 1 + 左孩子深度 + 右孩子深度
         */
        f(root)
        return maxPath
    }

    // 最大路径长度
    var maxPath: Int = 0
    private fun f(root: TreeNode?): Int {
        // 1 确定函数参数以及返回值
        // 2 确定终止条件
        if (root == null) {
            return 0
        }

        // 3 确定单层递归的遍历逻辑：左右中
        // 左
        val left_depth = f(root.left)

        // 右
        val right_depth = f(root.right)

        // 中
        // 当前节点的路径长度 = 当前节点的左孩子最大深度 + 当前的右孩子最大深度
        val current_Path = left_depth + right_depth
        // 更新全局的最大路径长度
        maxPath = Math.max(current_Path, maxPath)

        // 返回以当前节点为根节点的字数的最大深度
        return 1 + Math.max(left_depth, right_depth)
    }
}